#include "AVLTree.h"
#include <stdio.h>
#include <stdlib.h>

struct AVLNode {
    ElementType Element;
    AVLTree left;
    AVLTree right;
};

static int Max(int a, int b);
static int Height(AVLTree tree);
static Position RightSingleRotate(Position position);
static Position LeftSingleRotate(Position position);
static Position RightDoubleRotate(Position position);
static Position LeftDoubleRotate(Position position);

void TestAVLTree() {
    AVLTree tree = NULL;
    // int arr[] = {3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11,
    // 10,8,9};//用于验算插入
    int arr[] = {10, 5, 12, 6};  //用以验算删除操作

    //生成随机数，以组件平衡二叉树
    for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
        tree = Insert(tree, arr[i]);
        printf("%d\t", arr[i]);
    }

    //测试一系列操作
    printf("\nPreOder:\n");
    PreOrder(tree);
    printf("\nInOrder:\n");
    InOrder(tree);
    printf("\nPostOrder:\n");
    PostOrder(tree);
    printf("\n");

    puts("After deleting:");
    tree = Delete(tree, 12);
    InOrder(tree);

    //清空平衡树
    tree = MakeEmpty(tree);
}

AVLTree MakeEmpty(AVLTree tree) {
    if (!tree)
        return NULL;

    MakeEmpty(tree->left);
    MakeEmpty(tree->right);
    free(tree);
    return tree;
}

Position Find(AVLTree tree, ElementType x) {
    if (!tree)
        return NULL;

    if (tree->Element == x)
        return tree;
    else if (x < tree->Element)
        return Find(tree->left, x);
    else
        return Find(tree->right, x);
}

Position FindMin(AVLTree tree) {
    if (!tree)
        return NULL;
    return FindMin(tree->left);
}

Position FindMax(AVLTree tree) {
    if (!tree)
        return NULL;
    return FindMax(tree->right);
}

AVLTree Insert(AVLTree tree, ElementType x) {
    //常规二叉树的插入操作
    if (!tree) {
        tree = (AVLTree)malloc(sizeof(struct AVLNode));
        tree->left = NULL;
        tree->right = NULL;
        tree->Element = x;
        return tree;
    } else {
        if (x < tree->Element) {
            tree->left = Insert(tree->left, x);
            //依据平衡性进行旋转
            if (Height(tree->left) - Height(tree->right) == 2) {
                if (x < tree->left->Element) {
                    //进行单旋转
                    tree = RightSingleRotate(tree);
                } else {
                    //进行双旋转
                    tree = RightDoubleRotate(tree);
                }
            }
            return tree;
        }
        if (x > tree->Element) {
            tree->right = Insert(tree->right, x);
            //依据平衡性进行旋转
            if (Height(tree->right) - Height(tree->left) == 2) {
                if (x > tree->right->Element) {
                    tree = LeftSingleRotate(tree);
                } else {
                    tree = LeftDoubleRotate(tree);
                }
            }
            return tree;
        }
        return tree;
    }
}

//此处返回更新之后的树节点，为了处理要释放tree本身的情况，这是可以让上层父节点的对应指向更新为NULL
AVLTree Delete(AVLTree tree, ElementType x) {
    //采用递归方式进行删除

    //如果tree为空，无可删除对象，返回NULL
    if (!tree)
        return NULL;

    //基准情形
    if (x == tree->Element)
        //该节点即为待删除节点，分情况讨论
        //为叶子节点:释放该节点，返回NULL即可
        if (!tree->left && !tree->right) {
            free(tree);
            return NULL;
        }
        //两个孩子:将tree数值修改为右子树中的最小值，并删除右子树的最小值即可
        else if (tree->left && tree->right) {
            tree->Element = FindMin(tree->right)->Element;
            tree->right = Delete(tree->right, x);
            return tree;
        }
        //一个孩子:暂存子树根节点，释放tree节点，返回子树根节点即可
        else {
            AVLTree temp = tree->left ? tree->left : tree->right;
            free(tree);
            return temp;
        }

    //一般逻辑
    else if (x < tree->Element) {
        // x小于根节点的数值，向左子树删除
        tree->left = Delete(tree->left, x);

        //此处应判断平衡二叉树是否失衡
        if (Height(tree->right) - Height(tree->left) == 2) {
            if (tree->right->right) {
                //此时左旋转一次即可
                tree = LeftSingleRotate(tree);
            } else {
                //此时又-左双旋转即可
                tree = LeftDoubleRotate(tree);
            }
        }
        return tree;
    } else {
        // x大于根节点的数值，向右子树删除
        tree->right = Delete(tree->right, x);

        //此处应判断平衡二叉树是否失衡
        if (Height(tree->left) - Height(tree->right) == 2) {
            if (tree->left->left) {
                tree = RightSingleRotate(tree);
            } else {
                tree = RightDoubleRotate(tree);
            }
        }

        return tree;
    }
}

ElementType Retrive(Position position) {
    if (!position)
        return -1;
    return position->Element;
}

static int Height(AVLTree tree) {
    if (!tree)
        return -1;
    return 1 + Max(Height(tree->left), Height(tree->right));
}

void PreOrder(AVLTree tree) {
    if (!tree)
        return;
    printf("%d\t", tree->Element);
    PreOrder(tree->left);
    PreOrder(tree->right);
}

void PostOrder(AVLTree tree) {
    if (!tree)
        return;
    PostOrder(tree->left);
    PostOrder(tree->right);
    printf("%d\t", tree->Element);
}

void InOrder(AVLTree tree) {
    if (!tree)
        return;
    InOrder(tree->left);
    printf("%d\t", tree->Element);
    InOrder(tree->right);
}

static int Max(int a, int b) {
    return a >= b ? a : b;
}

static Position RightSingleRotate(Position position) {
    //判断合法性
    //如果本节点为空，不采取操作
    if (!position)
        return NULL;

    //如果不符合要求，不进行任何操作
    if (!position->left) {
        return position;
    }

    //符合要求，则进行旋转操作
    else {
        Position node1 = position, node2 = node1->left, node5 = node2->right;
        node1->left = node5;
        node2->right = node1;
        return node2;
    }
}

static Position LeftSingleRotate(Position position) {
    if (!position)
        return NULL;
    if (!position->right) {
        return position;
    } else {
        //满足此条件可以进行旋转
        Position node1 = position, node3 = node1->right, node5 = node3->left;
        node1->right = node5;
        node3->left = node1;
        return node3;
    }
}

static Position RightDoubleRotate(Position position) {
    if (!position)
        return NULL;

    position->left = LeftSingleRotate(position->left);
    return RightSingleRotate(position);
}

static Position LeftDoubleRotate(Position position) {
    if (!position)
        return NULL;
    position->right = RightSingleRotate(position->right);
    return LeftSingleRotate(position);
}